代码随想录 数组：209. 长度最小的子数组

力扣题目链接

文章讲解

题目：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

• 输入：s = 7, nums = [2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

思路

暴力解法就是先 for 循环区间左端点，左端点右移，然后里面 for 循环右端点右移，同时求和。区间和超了就求长度，把 result 和长度比较，更新 result，跳出右端点的循环。双层 for 循环，O(n^2)

滑动窗口

题目要求在数组中划分一个区间，区间的和满足要求，长度尽可能小。核心就是这个区间怎么变。是不是又有点像双指针，都是一个数组，在数组中划分一个区间，那么必然有左右端点。

我们理解一下，假设最靠左的一个最先满足条件的区间，我们有了，然后长度也有了，那么我们根据题目要求应该是使长度最小，那么该怎么移动这个窗口呢？长度不变着移动？还是右端点右移，扩展？右端点右移显然必定满足条件（因为里面都是正整数），而且长度变长，那么显然不是我们想要的结果，我们想要长度尽可能小。那左右端点整体移动？这样我们不知道是否满足条件，但是长度一定不变，那没有意义啊，我们想要找到最小长度，他不变的话我再怎么整体移动都没意义。那么我们就只有右端点不变左端点右移了，右移区间和一定减小，长度一定缩短，我们再判断和是否满足条件，这时如果不满足条件，该怎么办？那就扩大区间，怎么扩大？左端点再移回去？那不白干了，那只有右端点右移了，右移一位，长度是回复了，但和又增大了，得再判断条件。回到上一步，如果缩短长度后区间和仍满足条件？那继续左端点右移缩短长度呗。

以上是最原始的思路，精简以后就是：

1. 使用左右指针定义一个窗口
2. 右指针不断向右扩展，直到窗口和 ≥ s
3. 找到满足条件的窗口后，尝试缩小窗口（左指针右移）
4. 记录过程中满足条件的最小窗口长度

简洁思路就是，右指针右走，同时如果区间和满足要求了，求长度，左指针右移，这时区间缩小了，更新区间和。出来再次判断区间和是否满足要求

for(右指针右移){
    计算区间和
    while(区间和满足要求){
        求长度
        如果result小于长度，则更新否则不更新
        更新区间和，左指针右移
    }
}
return result；

int minSubArrayLen(int target, std::vector<int> &nums)
{
	int result = INT_MAX;
	int left = 0;
	int sum = 0;
	for (int right = 0; right < nums.size(); right++)
	{
		sum += nums[right];
		while (sum >= target)
		{
			int sublength = right - left + 1;
			result = result < sublength ? result : sublength;
			sum -=nums[left++];
		}
	}
	result = result == INT_MAX ? 0 : result;
	return result;
}